package algorithm.niuke;

public class G优美的数列 {
    /*
     * 假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N)
     * 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
     * 
     * 第 i 位的数字能被 i 整除 i 能被第 i 位上的数字整除 现在给定一个整数 N，请问可以构造多少个优美的排列？
     * 
     * 示例1:
     * 
     * 输入: 2 输出: 2 解释:
     * 
     * 第 1 个优美的排列是 [1, 2]: 第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除 第 2
     * 个位置（i=2）上的数字是2，2能被 i（i=2）整除
     * 
     * 第 2 个优美的排列是 [2, 1]: 第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除 第 2
     * 个位置（i=2）上的数字是1，i（i=2）能被 1 整除 说明:
     * 
     * N 是一个正整数，并且不会超过15。
     */
    public int countArrangement(int N) {
        // 首先，每位数字是1,2,3...N的排列是肯定可以的，所以如果知道N-1个数字的排列，那么N个数字的排列 c[n][n][n] += c[n-1][1...n-1][1...n-1]
        //其次，对于N能够整除的数 m,c[n-1]中 第m位为m的情况有c[n-1][m][m]种，那么c[n][m][n] += c[n-1][m][m] ;c[n][n][m] += c[n-1][m][m]; 
        int[] count = new int[N + 1];
        int[] end = new int[N + 1];
        end[1] = 1;
        count[1] = 1;
        for (int i = 2; i <= N; i++) {
            end[i] = count[i - 1];
            for (int k = 1; k < i; k++) {
                if (i % k == 0) {
                    count[i] += (end[i] - end[k]);
                }
            }
            count[i] += end[i];
        }
        return 1;
    }
}
